import java.util.ArrayList;
import java.util.HashMap;

/**
 * @description:
 * @Author: wuzhenbin
 * @CreateTime: 2025-02-15
 */
public class leetcode_138 {
    public static void main(String[] args) {
// 创建一个测试链表 [7,13,11,10,1]
        Node head = new Node(7);
        Node second = new Node(13);
        Node third = new Node(11);
        Node fourth = new Node(10);
        Node fifth = new Node(1);

        head.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;

        head.random = null;
        second.random = head;
        third.random = second;
        fourth.random = third;
        fifth.random = head;
        copyRandomList2(head);
    }

    public static Node copyRandomList2(Node head) {
        if (head == null) return null;
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        Node res = map.get(head);
        while (cur != null) {
            if(cur.next!=null){
                res.next = map.get(cur.next);
            }
            if(cur.random!=null){
                res.random = map.get(cur.random);
            }
            cur = cur.next;
            res = res.next;
        }
        //不要构建一个新的链表头
        return map.get(head);
    }
    //失败解法
    public Node copyRandomList(Node head) {
        Node resNode = new Node(head.val);
        Node res = resNode;
        Node resRandom = resNode;
        Node tmp = head;
        HashMap<Node, Node> map = new HashMap<>();
        while (head != null) {
            if (head.next != null) {
                resNode.next = new Node(head.next.val);
                map.put(head.next, resNode.next);
                //listRes.add(resNode.next);
            } else resNode.next = null;
            head = head.next;
            resNode = resNode.next;
        }
        while (tmp != null) {
            if (tmp.random != null) {
                resRandom.random = new Node(tmp.random.val);
                if (!map.containsKey(tmp.random)) {
                    resRandom.random = new Node(tmp.random.val);
                    map.put(tmp.random, resRandom.random);
                } else resRandom.random = map.get(tmp.random);
            } else resRandom.random = null;
            tmp = tmp.next;
            resRandom = resRandom.next;
        }
        return res;
    }

    public Node copyRandomList1(Node head) {
        if (head == null) {
            return null;  // 如果原链表为空，直接返回空
        }

        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;

        // 第一遍：复制链表的节点并保存原节点到新节点的映射
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        // 第二遍：设置新链表的next和random指针
        cur = head;
        while (cur != null) {
            Node newNode = map.get(cur);
            if (cur.next != null) {
                newNode.next = map.get(cur.next);  // 复制next指针
            }
            if (cur.random != null) {
                newNode.random = map.get(cur.random);  // 复制random指针
            }
            cur = cur.next;
        }

        return map.get(head);  // 返回复制链表的头节点
    }



    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
